# 
# Created by francklinson on 2021/7/29 AT 23:14.
#
from typing import List
from collections import Counter


class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 默认1更长
        if nums2 > nums1:
            self.intersect(nums2, nums1)
        ct = Counter(nums2)
        ans = list()
        for x in nums1:
            if x in ct.keys() and ct[x] > 0:
                ans.append(x)
                ct[x] -= 1
        return ans


class Solution2:
    # 双指针
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()

        length1, length2 = len(nums1), len(nums2)
        intersection = list()
        index1 = index2 = 0
        while index1 < length1 and index2 < length2:
            if nums1[index1] < nums2[index2]:
                index1 += 1
            elif nums1[index1] > nums2[index2]:
                index2 += 1
            else:
                intersection.append(nums1[index1])
                index1 += 1
                index2 += 1

        return intersection


if __name__ == '__main__':
    sol = Solution2()
    print(sol.intersect(nums1=[1, 2, 2, 1], nums2=[2, 2]))
    print(sol.intersect(nums1=[4, 9, 5], nums2=[9, 4, 9, 8, 4]))
    print(sol.intersect([1, 2, 2, 1], [2]))
